package com.sheyu;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author sheyu
 * @date 2020/8/27 9:18 上午
 */
public class Index_239 {

    /**
     * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *
     * 返回滑动窗口中的最大值。
     *
     *  
     *  建立双端队列，保证队列至多存在k个元素，且最开始的值是最大值，利用单调栈解决问题
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxValue = new int[nums.length-k+1];
        int start = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
           if (!deque.isEmpty()){
               if ((i-k+1)>deque.peekFirst()) {
                   deque.pollFirst();
               }
               if (deque.size()>=k){
                   deque.pollLast();
               }
            }
            while (!deque.isEmpty()&&nums[deque.peekLast()]<nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            if (i>=(k-1)){
                maxValue[start] = nums[deque.peekFirst()];
                start+=1;
            }
        }
        System.out.println(Arrays.toString(maxValue));
        return maxValue;
    }
//[3,3,5,5,6,7]
    public static void main(String[] args) {
        int[] nums = new int[]{1,3,1,2,0,5};
        int k=3;
        maxSlidingWindow(nums,k);
    }
}
